package 打牢基础30天.day05.my;

import 打牢基础30天.util.TreeUtil;

import java.util.Stack;

/**
 * @Author yaya
 * @Create 2024/6/15 8:35
 * Description:前中后序遍历一棵树
 */
public class Code01_PreInPosTraversal {


    /**
     * 递归方式实现前中后序
     *
     * @param root
     */
    public static void preOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        // 1
        System.out.print(root.value + "\t");
        preOrderRecur(root.left);
        // 2
        preOrderRecur(root.right);
        // 3
    }

    public static void inOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left);
        System.out.print(root.value + "\t");
        inOrderRecur(root.right);
    }

    public static void postOrderRecur(Node root) {
        if (root == null) {
            return;
        }

        postOrderRecur(root.left);
        postOrderRecur(root.right);
        System.out.print(root.value + "\t");
    }

    public static void preOrderUnRecur(Node root) {
        if (root == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node temp = null;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            System.out.print(temp.value + "\t");

            // 塞入子节点，先进后出，先塞right，后left
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
    }

    public static void inOrderUnRecur(Node root) {
        if (root == null){
            return;
        }
        // 先将树的所有子节点压入栈中，弹出一个对右子节点循环往复
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else {
                root = stack.pop();
                System.out.print(root.value + "\t");
                root = root.right;
            }
        }
    }

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);

        TreeUtil.printTree(head);

        // recursive
        System.out.println("==============recursive==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        postOrderRecur(head);
        System.out.println();
        System.out.println("==============UnRecursive==============");
        System.out.print("pre-order: ");
        preOrderUnRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderUnRecur(head);
        System.out.println();
    }
}
